//
// Description: 878. 线性同余方程
// Created by Loading on 2022/5/25.
//

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int ex_gcd(int a, int b, int &x, int &y) {
    if (!b) {
        // b = 0 时，最大公约数为 a，a * 1 + b * 0 = a 成立
        x = 1, y = 0;
        return a;
    }
    int d = ex_gcd(b, a % b, y, x);
    // by + a % b * x = d，展开得，ax + b(y - a / b * x) = d
    y -= a / b * x;

    return d;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = ex_gcd(a, m, x, y);
        if (b % d) {
            cout << "impossible" << endl;
        } else {
            cout << (LL) x * b / d % m << endl;
        }
    }

    return 0;
}